#include "avl_tree.h"
#include <stdio.h>
#include <stdlib.h>

// 节点所在的高度
#define HEIGHT(p) (((p) == NULL) ? -1 : ((p)->height))
// 平衡因子
#define HEIGHT_DIFF(p)                                                         \
  (((p) == NULL) ? 0 : (HEIGHT((p)->left) - HEIGHT((p)->right)))

// 创建新节点
avl_node new_node(int key) {
  avl_node node = (avl_node)malloc(sizeof(struct avl_node_t));

  if (node != NULL) {
    node->key = key;
    node->left = node->right = NULL;
    node->height = 0;

    printf("new key: %d\n", node->key);
  }
  return node;
}

// 返回左子树中的最小值
avl_node min_node(avl_node node) {
  avl_node temp = node;

  while (temp->left != NULL)
    temp = temp->left;

  return temp;
}

avl_node LL_rotation(avl_node root) {
  avl_node p = root->left;
  root->left = p->right;
  p->right = root;

  root->height = (__max(HEIGHT_DIFF(root->left), HEIGHT_DIFF(root->right)) + 1);
  p->height = (__max(HEIGHT_DIFF(p->left), HEIGHT_DIFF(p->right)) + 1);

  return p;
}
//                root        root
//               ↙            ↙
//             ㊣            ㊣            ① 临时存储新root
//            ╱ ╲           ╱ ╲           ② 处理新root的右(左)节点到旧root
//       p ⇢ ㊣  ㊣        ㊣  ㊣  ⇠ p     ③ 挂载旧root到新root的右(左)节点
//          ╱  ╲              ╱ ╲         ④ 返回新root
//         ㊣   ㊣            ㊣  ㊣
//        ╱                       ╲
//       ㊣                        ㊣
//    LL(左子树插入左孩子)         RR(右子树插入右孩子)

avl_node RR_rotation(avl_node root) {
  avl_node p = root->right;
  root->right = p->left;
  p->left = root;

  root->height = (__max(HEIGHT_DIFF(root->left), HEIGHT_DIFF(root->right)) + 1);
  p->height = (__max(HEIGHT_DIFF(p->left), HEIGHT_DIFF(p->right)) + 1);

  return p;
}
//
//             ㊣               ㊣             ㊣
//            ╱ ╲              ╱ ╲            ╱ ╲
//    root ⇢ ㊣  ㊣     root⇢ ㊣  ㊣      p⇢ ㊣  ㊣
//          ╱                ╱              ╱ ╲
//     p ⇢ ㊣           p ⇢ ㊣             ㊣  ㊣ ⇠root
//          ╲              ╱
//           ㊣           ㊣
//    LR(左子树插入左孩子)

// 先用子节点做父节点,先把左子树掰直成LL
avl_node LR_rotation(avl_node root) {
  root->left = RR_rotation(root->left);
  return LL_rotation(root);
}
//
//             ㊣               ㊣                   ㊣
//            ╱ ╲              ╱ ╲                  ╱ ╲
//           ㊣  ㊣ ⇠root     ㊣  ㊣ ⇠root          ㊣  ㊣ ⇠ p
//                ╲                ╲                  ╱ ╲
//            p ⇢ ㊣           p ⇢ ㊣         root ⇢ ㊣ ㊣
//               ╱                   ╲
//              ㊣                    ㊣
//    LR(左子树插入左孩子)

// 先用子节点做父节点,先把右子树掰直成RR
avl_node RL_rotation(avl_node root) {
  root->right = LL_rotation(root->right);
  return RR_rotation(root);
}

// 插入操作, 始终返回正在操作的节点
avl_node insert(avl_node node, int key) {
  if (node == NULL)
    return (new_node(key));

  if (key < node->key) {
    printf("visit left node: %d\n", node->key);
    // 递归直到插入节点,并在递归返回时执行if块后面的平衡操作
    node->left = insert(node->left, key);
  } else if (key > node->key) {
    printf("visit right node: %d\n", node->key);
    // 递归直到插入节点,并在递归返回时执行if块后面的平衡操作
    node->right = insert(node->right, key);
  }

  // 设置当前父节点的高度,并求得平衡因子
  node->height = (__max(HEIGHT_DIFF(node->left), HEIGHT_DIFF(node->right)) + 1);
  int balance = HEIGHT_DIFF(node);

  printf("Current node: %d , balance %d\n", node->key, balance);

  // LL
  if (balance > 1 && key < (node->left->key))
    return LL_rotation(node);

  // RR
  if (balance < -1 && key > (node->right->key))
    return RR_rotation(node);

  // LR
  if (balance > 1 && key > (node->left->key))
    node = LR_rotation(node);

  // RL
  if (balance < -1 && key < (node->right->key))
    node = RL_rotation(node);

  return node;
}

avl_node delete (avl_node node, int queryNum) {
  if (node == NULL)
    return node;

  if (queryNum < node->key)
    node->left = delete (node->left, queryNum);
  else if (queryNum > node->key)
    node->right = delete (node->right, queryNum);
  else { // 单孩子或没孩子
    if ((node->left == NULL) || (node->right == NULL)) {
      avl_node temp = node->left ? node->left : node->right;
      // 没有孩子
      if (temp == NULL) {
        temp = node;
        node = NULL;
      } else
        *node = *temp; // 仅仅复制值
      free(temp);
    } else {
      avl_node temp = min_node(node->right);
      node->key = temp->key; // 仅仅复制值过去
      // 删除最小值节点
      node->right = delete (node->right, temp->key);
    }
  }
    if (node == NULL)
      return node;

    node->height = (__max(HEIGHT_DIFF(node->left), HEIGHT_DIFF(node->right)) + 1);
    int balance = HEIGHT_DIFF(node);

    // LL
    if ((balance > 1) && (HEIGHT_DIFF(node->left) >= 0))
      return LL_rotation(node);

    // LR
    if ((balance > 1) && (HEIGHT_DIFF(node->left) < 0))
      node = LR_rotation(node);

    // RR
    if ((balance < -1) && (HEIGHT_DIFF(node->right) >= 0))
      return RR_rotation(node);

    // RL
    if ((balance < -1) && (HEIGHT_DIFF(node->right) < 0))
      node = RL_rotation(node);

   
   return node;
}


avl_node search(avl_node node, int queryNum) {
  if (node != NULL) {
    if (queryNum < node->key)
      node = search(node->left, queryNum);
    else if (queryNum > node->key)
      node = search(node->right, queryNum);
  }

  return node;
}

void pre_order(avl_node node) {
  if (node == NULL)
    return;

  printf("  %d  ", (node->key));
  pre_order(node->left);
  pre_order(node->right);
}

void in_order(avl_node node) {
  if (node == NULL)
    return;
  in_order(node->left);
  printf("  %d  ", (node->key));
  in_order(node->right);
}

void post_order(avl_node node) {
  if (node == NULL)
    return;
  post_order(node->left);
  post_order(node->right);
  printf("  %d  ", (node->key));
}
